package com.le.high.class1;

import org.junit.Test;

/**
 * 现有n1+n2种面值的硬币，其中前n1种为普通币，可以取任意枚，
 * 后n2种为纪念币， 每种最多只能取一枚，每种硬币有一个面值，
 * 问能用多少种方法拼出m的面值？
 * <p>
 * 思路：
 * 1. n1任意枚硬币并凑出 0,1,2,3,4,。。。元，
 * 2. n2拼凑出money-0,1,2,3...
 * 3. 各自平法的乘积之和就是最终答案
 * 两个动态规划的合并
 */
public class Problem03_MoneyWays {


    // 使用任意枚拼出money的方法数
    public static int ways(int[] arr, int money) {
        return process(arr, 0, money, 0);
    }

    public static int process(int[] arr, int i, int money, int finish) {
        if (i == arr.length) {
            return finish == money ? 1 : 0;
        }
        int res = 0;
        for (int zhang = 0; zhang * arr[i] <= money; zhang++) {
            res += process(arr, i + 1, money, finish + zhang * arr[i]);
        }
        return res;
    }

    public static int way1(int[] arr, int money) {
        // i,j : 0...i 上硬币随意使用，可以拼凑出J的方法数
        int[][] dp = new int[arr.length][money + 1];
        dp[0][0] = 1;
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < dp[0].length; i++) {
            dp[0][i] = i % arr[0] == 0 ? 1 : 0;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = j - arr[i] >= 0 ? dp[i - 1][j] + dp[i][j - arr[i]] : dp[i - 1][j];
            }
        }
        return dp[arr.length - 1][money];
    }

    // 使用0...i 范围类拼出money,每个币只能使用一次
    public static int way2(int[] arr, int money) {
        return process1(arr, 0, money);
    }
    public static int process1(int[] arr, int i, int rest) {
        if (i == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        return process1(arr, i + 1, rest) + process1(arr, i + 1, rest - arr[i]);
    }

    public static int way4(int[] arr, int money) {
        int[][] dp = new int[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i-1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
            }
        }
        return dp[arr.length - 1][money];
    }



    public static int moneyWays(int[] arbitrary, int[] onlyone, int money) {
        if (money < 0) {
            return 0;
        }
        if ((arbitrary == null || arbitrary.length == 0)
                && (onlyone == null || onlyone.length == 0)) {
            return money == 0 ? 1 : 0;
        }
        int[][] dparb = getDpArb(arbitrary, money);
        int[][] dpone = getDpOne(onlyone, money);
        if (dparb == null) {
            return dpone[dpone.length - 1][money];
        }
        if (dpone == null) {
            return dparb[dparb.length - 1][money];
        }
        int res = 0;
        for (int i = 0; i <= money; i++) {
            res += dparb[dparb.length - 1][i]
                    * dpone[dpone.length - 1][money - i];
        }
        return res;
    }

    public static int[][] getDpArb(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[][] dp = new int[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; arr[0] * j <= money; j++) {
            dp[0][arr[0] * j] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
            }
        }
        return dp;
    }

    public static int[][] getDpOne(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[][] dp = new int[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
            }
        }
        return dp;
    }


    @Test
    public void test() {
        int[] arr = {2, 1, 5, 3, 5};
        int money = 5;
//        System.out.println(ways(arr, money));
//        System.out.println(way1(arr, money));
        System.out.println(way2(arr, money));
        System.out.println(way4(arr, money));
    }
}
